1. Field of the Invention
The present invention relates to a radio network routing apparatus, and more particularly, to a protocol which reduces the amount of protocol traffic in mobile network routing.
2. Description of Related Art
Mobile networks typically use radios to communicate, but such radios are relatively slow data paths, as compared to wired networks or networks connected with fiber-optics.
In computer networks, the Open Shortest Path First (OSPF) routing algorithm is used for synchronizing the communication information in a computer network. The OSPF routing protocol, is a type of link-state protocol. A detailed discussion of link-state routing, including the OSPF protocol is included in Chapter 5 of Routing in Communications Networks by Martha Steenstrup and Chapter 5.2.2 of Computer Networks by Andrew S. Tanenbaum. OSPF provides a method of synchronizing databases in computer network “routers.” In OSPF, the router periodically advertises information describing its own database data (also referred to, herein, as link state data) to a neighboring router and includes a sequence number that the neighboring router can use to detect old or duplicate advertisements. The router increases the sequence number when it originates a new version of the advertisement. Thus, a larger sequence number signifies a more recent advertisement. The OSPF routing algorithm is also described in U.S. Pat. No. 5,913,921 (Tosey et al.) and U.S. Pat. No. 5,881,246 (Crawley et al.).
Mobile networks have been unable to use standard OSPF protocols to exchange internet routes and addresses. This is primarily due to the fact that OSPF protocols require constant route discovery through the use of HELLO messages. HELLO messages are packets of information dispersed by each node throughout the network to determine network topology. This HELLO traffic, alone, can potentially utilize all of the message capability (also referred to, herein, as “bandwidth”) of a mobile network having numerous nodes.
For example, a network consisting of four radio nodes (i.e., NODE A, NODE B, NODE C, AND NODE D) would generate several HELLO messages. NODE A would send a HELLO message to each of NODES B, C, and D; NODE B would send a HELLO message to each of NODES A, C, and D; NODE C would send a HELLO message to each of NODES A, B, and D; and NODE D would send a HELLO message to each of NODES A, B, and C. Each such HELLO message sent by a radio node must be answered with a reply HELLO message. Thus, the resulting number of HELLO messages (HM) for a network with N nodes can be determined by the following formula:HM=N×(N−1)×2
Accordingly, a network with four nodes would generate 24 HELLO messages. A network of 100 nodes would produce 19,800 HELLO messages. Clearly, the generation of so many HELLO messages in OSPF protocols has made the use of such protocols in mobile networks unfeasible.